#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// 朴素线段树，单点修改，区间查询，线段树上二分

template <typename S>
class segment_tree
{
private:
    vector<S> d;
    int _n, siz, lg;

    int ceil_pow2(int n)
    {
        int x = 0;
        while ((1U << x) < (unsigned int)(n))
            x++;
        return x;
    }

    void update(int k)
    {
        d[k] = d[k * 2] * d[k * 2 + 1];
    }

public:
    segment_tree() : segment_tree(0) {}
    explicit segment_tree(int n) : segment_tree(vector<S>(n, S::E)) {}
    explicit segment_tree(const vector<S> &v) : _n(v.size())
    {
        lg = ceil_pow2(_n);
        siz = 1 << lg;
        d = vector<S>(2 * siz, S::E);

        for (int i = 0; i < v.size(); i++)
        {
            d[siz + i] = v[i];
        }

        for (int i = siz - 1; i >= 1; i--)
        {
            update(i);
        }
    }

    void set(int p, S x)
    {
        p += siz;
        d[p] = x;
        for (int i = 1; i <= lg; i++)
            update(p >> i);
    }

    S get(int p) const
    {
        return d[p + siz];
    }

    // [l,r)
    S prod(int l, int r) const
    {
        S sml = S::E, smr = S::E;
        l += siz;
        r += siz;

        while (l < r)
        {
            if (l & 1)
                sml = sml * d[l++];
            if (r & 1)
                smr = d[--r] * smr;
            l >>= 1;
            r >>= 1;
        }
        return sml * smr;
    }

    S all_prod() const
    {
        return d[1];
    }

    // 寻找最大的 r 满足 [l,r) 满足 pred
    int max_right(int l, function<bool(S)> pred) const
    {
        if (l == _n)
            return _n;
        l += siz;
        S sm = S::E;
        do
        {
            while (l % 2 == 0)
                l >>= 1;
            if (!pred(sm * d[l]))
            {
                while (l < siz)
                {
                    l = 2 * l;
                    if (pred(sm * d[l]))
                    {
                        sm = sm * d[l];
                        l++;
                    }
                }
                return l - siz;
            }

            sm = sm * d[l];
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    // 寻找最小的 l 满足 [l,r) 满足 pred
    int min_left(int r, function<bool(S)> pred) const
    {
        if (r == 0)
            return 0;
        r += siz;
        S sm = S::E;
        do
        {
            r--;
            while (r > 1 && (r % 2))
                r >>= 1;
            if (!pred(d[r] * sm))
            {
                while (r < siz)
                {
                    r = 2 * r + 1;
                    if (pred(d[r] * sm))
                    {
                        sm = d[r] * sm;
                        r--;
                    }
                }
                return r + 1 - siz;
            }

            sm = d[r] * sm;
        } while ((r & -r) != r);
        return 0;
    }
};
